
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}


void AdjustDown(int* a, size_t size, size_t root)
{
    size_t parent=root;
    //假设需要交换的是左孩子
    size_t child=parent*2+1;
    while(child<size)
    {
        //如果右孩子存在且比右孩子小
        if(child+1<size&&a[child+1]<a[child])
        {
            child++;
        }
        if(a[child]>a[parent])
        {
            Swap(&a[child],&a[parent]);
            parent=child;
            child=parent*2+1;
        }
        else
        {
            break;
        }
    }
}


int PartSort3(int* a, int left, int right)
{
	int keyi = left;
	int prev = left, cur = prev + 1;
	while (cur<=right)
	{
        //遇见比自己小的就交换，同时避免不必要的交换
		if (a[cur] <a[keyi]&&a[++prev]!=a[cur])
			swap(&a[cur], &a[prev]);
		cur++;
	}
	swap(&a[prev], &a[keyi]);
	return prev;
}


void _MergeSortNonR(int* a, int begin,int end,int*tmp)
{
    if(begin>=end)
    	return ;
    int mid=(begin+end)/2;
    //如果不按照[begin,mid][mid+1,end]的方式划分，可能会出现死循环
     _MergeSortNonR(a,begin,mid,tmp);
     _MergeSortNonR(a,mid+1,end,tmp);
    //对已经排好序的两个区间进行归并排序
    int begin1=begin,end1=mid;
    int begin2=mid+1,end2=end;
    int index=begin;
    while(begin1<=end1&&begin2<=end2)
    {
        if(a[begin1]<a[begin2])
            tmp[index++]=a[begin1++];
        else
            tmp[index++]=a[begin2++];
    }
    while(begin1<=end1)
        tmp[index++]=a[begin1++];
    while(begin2<=end2)
        tmp[index++]=a[begin2++];
    memcpy(a+begin,tmp+begin,(end-begin+1)*sizeof(int));
}


void InsertSort(int* a, int n);
void BubbleSort(int* a, int n);
void ShellSort(int*a,int n);
void SelectSort(int*a,int n);
void HeapSort(int*a,int n);
void QuickSort(int*a,int begin,int end);
void MergeSortNonR(int* a, int n);
void CounSort(int*a,int n);